package Runde5;

public abstract class SortedTree<A extends Comparable<? super A>> extends Tree<A> {
	
	/**
	 * @precondition root != null
	 * @postcondition Creates a new binary search tree with the root labeled by the given object.
	 */
	public SortedTree(A root) {
		super(root);
	}
	
	/**
	 * @precondition label != null
	 * @postcondition Adds a new node with given label to the tree, maintaining its sorting.
	 */
	public void add(A label) {
		recAdd(label, root);
	}
	
	/**
	 * Auxiliary function for add().
	 * @precondition label and node both must not be null.
	 * @postcondition Adds a node to the tree while maintaining the sorting.
	 * @param label The label of the new node to add.
	 * @param node The root of the tree the node is to be added to.
	 */
	private void recAdd(A label, Node node) {
		if (label.compareTo(node.getLabel()) < 0) {
			if (node.getLeftChild() == null) {
				node.setLeftChild(new Node(label));
			} else {
				recAdd(label, node.getLeftChild());
			}
		} else {
			if (node.getRightChild() == null) {
				node.setRightChild(new Node(label));
			} else {
				recAdd(label, node.getRightChild());
			}
		}
	}
	
	/**
	 * @precondition label != null
	 * @postcondition Returns Boolean-Iterator which describes the path from the root of the tree to a node with the given label (true=right, false=left),
	 * 					returns null if no matching node was found
	 */
	public Iter<Boolean> search(A node) {
		Iter<Boolean> it = suche(node, root, new List<Boolean>()); 
		if (it == null) {
			return null;
		} else {
			return it;
		}
	}
	
	/**
	 * Auxiliary method for search().
	 * 
	 * @precondition None of the parameters may be null.
	 * @postcondition Returns an iterator over a list of boolean values, see search() for exact description. 
	 * @param label The label of the node to search for.
	 * @param node The root of the tree to search in.
	 * @param list List with the "directions" to the node (so far).
	 */
	private Iter<Boolean> suche(A label, Node node, List<Boolean> list) {		
		
		if(node == null) {
			return null;
		} else if (label.compareTo(node.getLabel()) == 0) {
			return list.iterator();
		} else if (label.compareTo(node.getLabel()) < 0) {
			list.add(false);
			return suche(label, node.getLeftChild(), list);
		} else if (label.compareTo(node.getLabel()) > 0) {
			list.add(true);
			return suche(label, node.getRightChild(), list);
		} else {
			return null;
		}
	}
	
}
